import random

class Node:
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
        self.down = None


class Skiplist:

    def __init__(self):
        self.maxLevel = 8
        self.leftTower = []
        self.rightTower = []
        for i in range(self.maxLevel):
            left = Node(float('-inf'))
            right = Node(float('inf'))
            left.right = right
            right.left = left
            self.leftTower.append(left)
            self.rightTower.append(right)
            if i > 0:
                left.down = self.leftTower[i-1]
                right.down = self.rightTower[i-1]

    def search(self, target: int) -> bool:
        node = self.searchNode(target)
        return node != None

    def searchNode(self, target: int) -> Node:
        currNode = self.leftTower[-1]

        while currNode != None:
            if target == currNode.value:
                return currNode
            elif target > currNode.value:
                right = currNode.right
                if target < right.value:
                    currNode = currNode.down
                elif target == right.value:
                    return right
                else:
                    currNode = right
        return None

    def add(self, num: int) -> None:
        currNode = self.leftTower[-1]

        theLefts = []
        theLefts.append(currNode)
        while currNode != None:
            right = currNode.right
            if num < right.value:
                if currNode != None:
                    theLefts.append(currNode)
                currNode = currNode.down
            else:
                currNode = right

        level = self.randomLevel()
        prevNode = None
        for i in range(level):
            node = Node(num)
            index = -1 * (i + 1)
            node.left = theLefts[index]
            node.right = theLefts[index].right
            theLefts[index].right.left = node
            theLefts[index].right = node
            node.down = prevNode
            prevNode = node


    def erase(self, num: int) -> bool:
        node = self.searchNode(num)
        if node == None:
            return False
        currNode = node
        while currNode != None:
            currNode.left.right = currNode.right
            currNode.right.left = currNode.left
            currNode = currNode.down
        return True

    # 层数是从 1 开始的
    def randomLevel(self):
        for i in range(self.maxLevel):
            if random.randint(0, 1):
                return i + 1
        return self.maxLevel

# skiplist = Skiplist();
# skiplist.add(1);
# skiplist.add(2);
# skiplist.add(3);
# print(skiplist.search(0)) # 返回 false
# skiplist.add(4);
# print(skiplist.search(1)) # 返回 true
# print(skiplist.erase(0))  # 返回 false，0 不在跳表中
# print(skiplist.erase(1))  # 返回 true
# print(skiplist.search(1)) # 返回 false，1 已被擦除


s = Skiplist()
s.add(3)
s.add(14)
s.add(3)
s.add(18)
s.add(1)
s.add(18)
s.add(17)
s.add(8)
s.add(5)
s.add(16)
s.add(3)
print(s.search(10)) # false
print(s.search(9))  # false
print(s.erase(14))  # true
print(s.erase(13))  # false
s.add(18)
print(s.search(11))  # false
print(s.erase(16))   # true
print(s.search(1))   # true
s.add(7)
s.add(5)
print(s.erase(12))   # false
print(s.erase(11))   # false
s.add(20)
print(s.erase(17))   # true
print(s.erase(2))    # false
print(s.erase(1))    # true
print(s.search(4))   # false
print(s.search(17))   # false
